/*
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/
 */
import java.util.Stack;

public class Solution84 {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack=new Stack<>();
        int[] left=new int[heights.length];
        for (int i=0;i<heights.length;i++){
            while (!stack.isEmpty() && heights[i]<=heights[stack.peek()]){
                stack.pop();
            }
            left[i]=stack.isEmpty()?-1:stack.peek();
            stack.push(i);
        }
        stack.clear();
        int[] right=new int[heights.length];
        for (int i=heights.length-1;i>=0;i--){
            while (!stack.isEmpty() && heights[i]<=heights[stack.peek()]){
                stack.pop();
            }
            right[i]=stack.isEmpty()?heights.length:stack.peek();
            stack.push(i);
        }
        int ans=0;
        for (int i=0;i<heights.length;i++){
            ans=Math.max(ans,heights[i]*(right[i]-left[i]-1));
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution84().largestRectangleArea(new int[]{2,1,5,6,2,3}));
    }
}
